package work.month06.day08;

import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

/**
 * @date 2020/06/08
 * @author 王光浩
 * @introduction 手写双向链表
 * 		要求方法：
 * 			（1）public String toString() 
 * 			（2）public boolean add( E element ) // 实现将元素添加到 链表 末尾
 * 			（3）public void add( int index, E element ) //【找到指定的索引，并将元素插入到该位置】
 * 			（4）public E remove( int index ) //【根据索引删除指定位置的元素】
 * 			（5）public E get(int index)			//根据下标获取对应的val值
 * 			（6）public void clear() 			//将 链表清空
 * 			（7）public int size()				//返回链表中元素的个数
 * 			（8）public boolean isEmpty()		//判断链表是否为 空
 * 			（9）public boolean remove(Object o) //根据对象删除指定元素
 */
public class NodeList<T> implements List<T>{
	
//========  实例字段  =====================
	
	/**
	 * 实例内部类，用于保存节点信息
	 * @author 王光浩
	 * @param <E>
	 */
	private class Node<E> {
		private Node<E> next;
		private Node<E> pre;
		private E value;
		Node(Node<E> next, Node<E> pre, E value){
			this.next = next;
			this.pre = pre;
			this.value = value;
		}
	}
	
	private Node<T> first; //指向双向链表的第一个节点
	private Node<T> last;  //指向双向链表的最后一个节点
	
	private int size = 0;  //保存链表中元素的个数

// ================  构造方法  ========================
	public NodeList() {
		
	}
	
// ================  实例方法  ==========================
	/**
	 * 返回 链表中元素的个数
	 */
	@Override	
	public int size() {
		return this.size;
	}

	/**
	 * 判断链表是否为空
	 */
	@Override
	public boolean isEmpty() {
		return size == 0;
	}	

	/**
	 * 将链表中的元素清空
	 */
	@Override
	public void clear() {
		size = 0;
		first = null;
		last = null;
	}

	/**
	 * 在此链表的尾部添加一个元素
	 */
	@Override
	public boolean add(T e) {
		Node<T> node = new Node<T>(null, null, e);
		//当链表为空时
		if (first == null) {
			first = node;
		} else { //链表不为空
			node.pre = last;
			last.next = node;			
		}
		last = node;
		size++;
		return true;
	}
	
	/**
	 * 在指定元素的下标前添加元素，下标从 0 开始，0<=index && index <= size，当 index == size 时表示在链表的末尾
	 * 添加元素
	 */
	@Override
	public void add(int index, T element) {
		//当 index == size 时，在链表的尾部添加节点，需要注意的是当链表为空时，调用 add（T e）方法
		if (index == size) {
			add(element);
			return;
		}
		Node<T> node = getNode(index);
		Node<T> newNode = new Node<T>(null,null,element);
		if (node != first) {
			newNode.pre = node.pre;
			node.pre.next = newNode;
		} else { //当需要在链表的首部添加数据时
			first = newNode;
		}
		newNode.next = node;
		node.pre = newNode;
		size++;
		return;
	}
	
	/**
	 * 在链表中删除与指定对象具有相同 value 的节点（只删除第一次出现的）
	 */
	@Override
	public boolean remove(Object o) {
		Node<T> node = first;
		if (o == null) {
			for (; node != null; node = node.next) {
				if (node.value == null) {
					unlink(node);
					return true;
				}
			}
		} 
		for (; node != null; node = node.next) {
			if (o.equals(node.value)) {
				unlink(node);
				return true;
			}
		}
		return false;
	}
		
	/**
	 * 根据 下标删除元素
	 */
	@Override
	public T remove(int index) {
		Node<T> node = getNode(index);
		unlink(node);
		return node.value;
	}
	
	/**
	 * 设置相应下标元素值
	 */
	@Override
	public T set(int index, T element) {
		Node<T> node = getNode(index);
		T oldValue = node.value;
		node.value = element;
		return oldValue;
	}
	
	/**
	 * 根据下标获取对应的 value
	 */
	@Override
	public T get(int index) {
		return getNode(index).value;
	}
	
	/**
	 * 将链表中的内容按照存储的顺序进行输出
	 */
	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		sb.append('[');
		Node<T> node = first;
		for (int i = 0; i < size-1; i++) {
			sb.append(node.value+",");
			node = node.next;
		}
		if (node != null)
			sb.append(node.value);
		sb.append(']');
		return sb.toString();
	}

	/**
	 * 根据下标返回对应的节点（下标从 0 开始）
	 * @param index
	 * @return 返回对应的节点信息
	 * @throws 当下标越界时，将会抛出RuntimeException 
	 */
	private Node<T> getNode(int index) {
		//防止下标越界
		if (index < 0 || index >= size)
			throw new RuntimeException("下标越界，index 不能小于0或大于链表size");
		Node<T> node = first;
		int count = 0;
		//根据下标寻找对应的Node节点
		while (node != null) {
			if (count == index)
				return node;
			node = node.next;
			count++;
		}
		return null;
	}	
	
	/**
	 * 在链表中将该节点解开
	 * @param node
	 */
	private void unlink(Node<T> node) {
		if (size == 1) {
			clear();
			return;
		}
		if (node == first) {
			first = node.next;
			node.next.pre = null;
			node.next = null;
		} else if (node == last) {
			last = node.pre;
			node.pre.next = null;
			node.pre = null;
		} else {
			node.next.pre = node.pre;
			node.pre.next = node.next;
			node.pre = null;
			node.next = null;
		}
		size--;
	}
	
// ================  不需要实现的方法    ============================
	@Override
	public boolean containsAll(Collection<?> c) {
		return false;
	}
	@Override
	public boolean addAll(Collection<? extends T> c) {
		return false;
	}
	@Override
	public boolean addAll(int index, Collection<? extends T> c) {
		return false;
	}
	@Override
	public boolean removeAll(Collection<?> c) {
		return false;
	}
	@Override
	public boolean retainAll(Collection<?> c) {
		return false;
	}
	@Override
	public int indexOf(Object o) {
		return 0;
	}
	@Override
	public int lastIndexOf(Object o) {
		return 0;
	}
	@Override
	public ListIterator<T> listIterator() {
		return null;
	}
	@Override
	public ListIterator<T> listIterator(int index) {
		return null;
	}
	@Override
	public List<T> subList(int fromIndex, int toIndex) {
		return null;
	}
	@Override
	public Iterator<T> iterator() {
		return null;
	}
	@Override
	public Object[] toArray() {
		return null;
	}
	@Override
	public <T> T[] toArray(T[] a) {
		return null;
	}
	@Override
	public boolean contains(Object o) {
		return false;
	}

}
